package Algorithms;

import java.util.Scanner;

public class mergesort {
public static void sort(Comparable[]a) {
	sorts(a,0,a.length-1);
}
private static void merge(Comparable[]a,int lo,int mid,int hi) {
	Comparable[]aux=new Comparable[a.length];
	int i=lo,j=mid+1;
	for(int k=lo;k<=hi;k++)aux[k]=a[k];
	for(int k=lo;k<=hi;k++) {
		if(i>mid) {a[k]=aux[j++];}
		else if(j>hi) {a[k]=aux[i++];}
		else if(less(aux[i], aux[j])) {a[k]=aux[i++];}
		else {a[k]=aux[j++];}
	}
}
private static void sorts(Comparable[]a,int lo,int hi) {
	if(lo>=hi)return;
	int mid=lo+(hi-lo)/2;
	sorts(a, lo, mid);
	sorts(a, mid+1, hi);
	merge(a, lo, mid, hi);
}
private static boolean less(Comparable v,Comparable w) {
	return v.compareTo(w)<0;
}
public static boolean isSorted(Comparable[]a,int lo,int hi) {
	for(int i=lo;i<=hi;i++) {
		if(less(a[i], a[i+1]))return false;
	}
	return true;
}
public static void show(Comparable[] a) {
	for(int i=0;i<a.length;i++) {
		System.out.print(a[i]+" ");
	}
	System.out.println("");
}
public static void main(String[]args) {
	Scanner scanner=new Scanner(System.in);
	String[]a=new String[10];
	for(int i=0;i<10;i++) {
		a[i]=scanner.next();
	}
	show(a);
	sort(a);
	show(a);
}
}
